Search results for " tree search"
showing 6 items of 6 documents
An AI for dominion based on Monte-Carlo methods
2014
Masteroppgave i Informasjons- og kommunikasjonsteknologi IKT590 Universitetet i Agder 2014 To the best of our knowledge there exists no Arti_cial Intelligence (AI)for Dominion which uses Monte Carlo methods, that is competitive on ahuman level. This thesis presents such an AI, and tests it against someof the top Dominion strategies available. Although in a limited testingenvironment, the results show that our AI is capable of competing withhuman players, while keeping processing time per move at an acceptablelevel for human players. Although the approach for our AI is built onprevious knowledge about Upper Con_dence Bounds (UCB) and UCBapplied to Trees (UCT), an approach for handling the st…
Robust Assembly Assistance Using Informed Tree Search with Markov Chains
2022
Manual work accounts for one of the largest workgroups in the European manufacturing sector, and improving the training capacity, quality, and speed brings significant competitive benefits to companies. In this context, this paper presents an informed tree search on top of a Markov chain that suggests possible next assembly steps as a key component of an innovative assembly training station for manual operations. The goal of the next step suggestions is to provide support to inexperienced workers or to assist experienced workers by providing choices for the next assembly step in an automated manner without the involvement of a human trainer on site. Data stemming from 179 experiment partici…
Fuzzified Game Tree Search – Precision vs Speed
2012
Most game tree search algorithms consider finding the optimal move. That is, given an evaluation function they guarantee that selected move will be the best according to it. However, in practice most evaluation functions are themselves approximations and cannot be considered "optimal". Besides, we might be satisfied with nearly optimal solution if it gives us a considerable performance improvement. In this paper we present the approximation based implementations of the fuzzified game tree search algorithm. The paradigm of the algorithm allows us to efficiently find nearly optimal solutions so we can choose the "target quality" of the search with arbitrary precision --- either it is 100% (pr…
An A* Based Semantic Tokenizer for Increasing the Performance of Semantic Applications
2013
Semantic Applications (SAs) makes use of ontolo- gies and their performance can depend on the syntactic labels of the modeled entities; even if several approaches have been devised to formalize ontologies, no formal approaches have been devised for naming their constituents, which look as long word concatenations without any particular separation. We present a novel semantic tokenizer that finds the sub-words through an application of the A* based search algorithm; the A* functions rely on a set of linguistic criteria and on the meta-cognitive perspective of the activity of reading.
Fuzzified Tree Search in Real Domain Games
2011
Fuzzified game tree search algorithm is based on the idea that the exact game tree evaluation is not required to find the best move. Therefore, pruning techniques may be applied earlier resulting in faster search and greater performance. Applied to an abstract domain, it outperforms the existing ones such as Alpha-Beta, PVS, Negascout, NegaC*, SSS*/ Dual* and MTD(f). In this paper we present experimental results in real domain games, where the proposed algorithm demonstrated 10 percent performance increase over the existing algorithms.
AIs for Dominion Using Monte-Carlo Tree Search
2015
Dominion is a complex game, with hidden information and stochastic elements. This makes creating any artificial intelligence AI challenging. To this date, there is little work in the literature on AI for Dominion, and existing solutions rely upon carefully tuned finite-state solutions. This paper presents two novel AIs for Dominion based on Monte-Carlo Tree Search MCTS methods. This is achieved by employing Upper Confidence Bounds UCB and Upper Confidence Bounds applied to Trees UCT. The proposed solutions are notably better than existing work. The strongest proposal is able to win 67% of games played against a known, good finite-state solution, even when the finite-state solution has the u…